def summit():
    pass


if __name__ == '__main__':
    summit()

from typing import Dict


def rectify_str(_str: str) -> Dict:
    """
    给定一个题目定义的多项式字符串,将其放到一个dict中{幂:系数}
    :param _str: 题目定义的多项式字符串
    """
    result = {}
    numbers = _str[2:].split()
    for i in range(0, len(numbers) - 1, 2):
        result[int(numbers[i])] = float(numbers[i + 1])
    return result


def rectify_data(data: Dict) -> str:
    """
    将求解用的数据结构，转换为题目定义的多项式字符串
    :param data: 由{幂:系数}组成的Dict
    """
    data = {k: data[k] for k in sorted(data.keys(), reverse=True)}

    if len(data) > 0:
        numbers = map(
            lambda x: f'{x:.1f}' if isinstance(x, float) else str(x),
            sum(zip(data.keys(), data.values()), ())
        )
        return f"{len(data)} {' '.join(numbers)}"
    else:
        return "0"


def cal_poly(a: Dict, b: Dict) -> Dict:
    """
    计算两项多项式的和，结果保留1位小数
    :param a: 由{幂:系数}组成的Dict
    :param b: 由{幂:系数}组成的Dict
    """
    result = {}
    a_keys = list(a.keys())
    b_keys = list(b.keys())
    for e in set(a_keys + b_keys):
        if (e in a_keys) and (e in b_keys):
            c = a[e] + b[e]
            if c != 0:
                result[e] = c
        elif e in a_keys:
            if 0 != a[e]:
                result[e] = a[e]
        elif e in b_keys:
            if 0 != b[e]:
                result[e] = b[e]
    return result


def summit():
    print(rectify_data(cal_poly(rectify_str(input()), rectify_str(input()))), end='')


if __name__ == '__main__':
    summit()

from typing import Dict, List


def solution(graph: List[List[int]], source: int, destination: int, teams: Dict[int, int]) -> str:
    nodes = len(graph)
    infos = {
        "isVisited": [False] * nodes,  # 访问位
        "shortestLen": [float("inf")] * nodes,  # 最短路径的长度
        "parent": [None] * nodes,  # 最短路径的父亲节点
        "shortestNum": [0] * nodes,  # 多少条最短路径
        "maxTeams": [0] * nodes  # 最大的资源数
    }

    infos["isVisited"][source] = True  # 起点的访问位为True
    infos["shortestLen"][source] = 0  # 起点的最短路径的长度为0
    infos["maxTeams"][source] = teams[source]  # 起点的最大资源数为其自己的资源
    infos["shortestNum"][source] = 1  # 起点的最短路径为1，为了保证后面的逻辑能够正常运行

    # 现在扫描的节点
    now = source

    # 还有未访问的点
    while not all(infos["isVisited"]):
        # for i in zip(*infos) 转置的效率会怎么样
        # 扫描现在节点的邻居
        for neighbor in range(nodes):
            # 存在一条边
            if graph[now][neighbor] != 0 and not infos["isVisited"][neighbor]:
                temp = infos["shortestLen"][now] + graph[now][neighbor]
                if infos["shortestLen"][neighbor] > temp:  # 当前的路径更小，替换信息表中的路径
                    infos["shortestLen"][neighbor] = temp
                    totalTeams = infos["maxTeams"][now] + teams[neighbor]
                    if infos["maxTeams"][neighbor] < totalTeams:  # 如果这条最短路径上的物资更多
                        infos["maxTeams"][neighbor] = totalTeams
                    infos['parent'][neighbor] = now
                    infos["shortestNum"][neighbor] = infos["shortestNum"][now]  # 重置最短路径数
                    # 如果相等且已经访问，且这条路径和之前的最短路径不一样,最短路径数+1
                elif infos["shortestLen"][neighbor] == temp and infos["parent"][neighbor] != now:
                    infos["shortestNum"][neighbor] += infos["shortestNum"][now]
                    totalTeams = infos["maxTeams"][now] + teams[neighbor]
                    if infos["maxTeams"][neighbor] < totalTeams:  # 如果这条最短路径上的物资更多
                        infos["maxTeams"][neighbor] = totalTeams

        #  找到当前未访问且路径最短的节点
        minIdx = -1
        minWeight = float("inf")
        for i in range(nodes):
            if (infos["isVisited"][i] is False) and (infos["shortestLen"][i] < minWeight):
                minIdx = i
                minWeight = infos["shortestLen"][i]

        # 更新visited节点
        infos["isVisited"][minIdx] = True
        now = minIdx

    return f"{infos['shortestNum'][destination]} {infos['maxTeams'][destination]}"


def get_cities_roads_source_destination(string: str) -> List[int]:
    """
    :param string: "citiesNum roadsNum source destination"
    :return: [citiesNum, roadsNum, source, destination]
    """
    return list(map(int, string.split()))


def get_teams_size(string: str) -> Dict[int, int]:
    """
    :param string: "team1 team2 ... teamN"
    :return: {team_i: size}
    """
    return {
        idx: int(i) for idx, i in enumerate(string.split())
    }


def add_edge(graph: List[List[int]], string: str) -> None:
    """
    :param graph: 邻接矩阵表示的图
    :param string: "node1 node2 weight"
    """
    edge = list(map(int, string.split()))
    graph[edge[0]][edge[1]] = edge[2]
    graph[edge[1]][edge[0]] = edge[2]


def summit() -> str:
    cities,  roads, source, destination = get_cities_roads_source_destination(input())
    graph = [[0] * cities for _ in range(cities)]
    teams = get_teams_size(input())
    while roads > 0:
        add_edge(graph, input())
        roads -= 1
    print(solution(graph, source, destination, teams), end="\n")


if __name__ == '__main__':
    summit()

import unittest
from typing import Dict, List, Tuple
import queue


def solution(tree: Dict[int, List[int]]) -> str:
    """
    :param tree: 孩子表示法：见readme
    :return:
    """
    q = queue.Queue()
    answer = dict()
    result = []
    childLevel = 0
    q.put((1, 1))  # 根节点进入队列,(节点编号，节点所在层号)
    # 进行层次遍历, 返回每一层的叶子节点数
    while not q.empty():
        head = q.get()  # 队列的头元素
        if len(tree[head[0]]) == 0:  # 检查头元素是不是叶子节点
            emptyNum = answer.get(head[1], 0)
            answer[head[1]] = emptyNum + 1  # 该层叶子节点数+1
        else:  # 让头元素的孩子节点进入队列
            childLevel = head[1] + 1
            for child in tree[head[0]]:
                q.put((child, childLevel))
    for i in range(1, childLevel+1):
        result.append(str(answer.get(i, 0)))
    if childLevel == 0:
        result = ["1"]
    return " ".join(result)


def get_nodes_and_not_leaves_num(string: str) -> List[int]:
    """
    :param string: "节点数 叶子节点数"
    :return: [节点数, 叶子节点数]
    """
    return list(map(int, string.split()))


def get_children(string: str) -> Tuple[int, List[int]]:
    """
    :param string: "ID K ID[1] ID[2] ... ID[K]"
    :return: 父亲节点，[ID[1] ID[2] ... ID[K]]
    """
    nodes = list(map(int, string.split()))
    return nodes[0], nodes[2:]


def summit() -> str:
    nodes, notLeaves = get_nodes_and_not_leaves_num(input())
    tree = {
        i: [] for i in range(nodes+1)
    }
    while notLeaves > 0:
        parent, children = get_children(input())
        tree[parent].extend(children)
        notLeaves -= 1
    print(solution(tree), end="\n")


if __name__ == '__main__':
    summit()

from typing import List


def summit():
    string = input()
    numToEn = {
        0: "zero",
        1: "one",
        2: "two",
        3: "three",
        4: "four",
        5: "five",
        6: "six",
        7: "seven",
        8: "eight",
        9: "nine",
    }
    nums: List[int] = [int(i) for i in string]
    print(" ".join([numToEn[int(i)] for i in str(sum(nums))]), end="")


if __name__ == '__main__':
    summit()

from typing import List


def extract_details(name: str, signIn: str, signOut: str):
    return {
        "name": name,
        "signIn": sum([60 ** (2 - idx) * int(i) for idx, i in enumerate(signIn.split(":"))]),
        "signOut": sum([60 ** (2 - idx) * int(i) for idx, i in enumerate(signOut.split(":"))]),
    }


def solution(memberInfos: List):
    unlock = f"{sorted(memberInfos, key=lambda x: x['signIn'])[0]['name']}"
    lock = f"{sorted(memberInfos, key=lambda x: x['signOut'])[-1]['name']}"

    return f"{unlock} {lock}"


def summit():
    memberInfos = []
    members = int(input())
    while members > 0:
        string = input()
        memberInfos.append(
            extract_details(*(string.split()))
        )
        members -= 1
    print(solution(memberInfos), end="")


if __name__ == '__main__':
    summit()

from typing import List
from functools import reduce


def next_positive_in_result(result: List[List[int]], now: int) -> int:
    """
    :param result:
    :param now: 现在指针的位置
    :return:
    """
    for i in range(now+1, len(result)):
        if sum(result[i]) >= 0:
            return i
    return -1


def split_positive_negative(nums: List[int]) -> List[List[int]]:
    result = []
    # 正负分割
    positive = False if nums[0] < 0 else True
    start = 0
    end = 0
    isChange = False
    for i in range(1, len(nums)):
        iPositive = False if nums[i] < 0 else True
        # 如果符号不相等
        if not(positive is iPositive):
            result.append(nums[start:i].copy())
            start = i
            positive = not positive
            isChange = True
    # if start == len(nums) - 1:  # 考虑最后一位
    result.append(nums[start:].copy())  # 帮前面的循环收尾
    if not isChange:  # 符号都一样
        return [nums]

    return result


def delete_zero_at_last(l: List[int]) -> None:
    if sum(l) == 0:  # 只有0不考虑
        return None
    while l[-1] == 0:
        del l[-1]


def merge_positive(result: List[List[int]]) -> None:
    # 试图合并正负序列
    isChange = False  # result列表有没有改变
    now = 0 if sum(result[0]) > 0 else next_positive_in_result(result, 0)
    while now != -1:
        nextPositiveIdx = next_positive_in_result(result, now)
        if nextPositiveIdx == -1:
            break
        merge = reduce(lambda a, b: a + sum(b), result[now:nextPositiveIdx+1], 0)
        if sum(result[now]) < merge and sum(result[nextPositiveIdx]) <= merge:  # 保证i最小
            result.insert(now, reduce(lambda a, b: a + b, result[now:nextPositiveIdx+1], []))
            del result[now+1:nextPositiveIdx+2]
            isChange = True
        else:
            isChange = False
            now = nextPositiveIdx
            nextPositiveIdx = next_positive_in_result(result, now)
        if isChange:
            now = nextPositiveIdx
            nextPositiveIdx = next_positive_in_result(result, now)


def find_max_sequence(result: List[List[int]]) -> int:
    maxIdx = 0
    for i in range(len(result)):
        if sum(result[i]) > sum(result[maxIdx]):
            maxIdx = i
    return maxIdx


def solution(nums: List[int]) -> str:
    """
    :param nums:
    :return: "maxSum maxSequenceFirstItem maxSequenceLastItem"
    """
    result = split_positive_negative(nums)
    if len(result) == 1 and sum(result[0]) <= 0:  # 全是负数
        return f"0 {result[0][0]} {result[0][-1]}"
    merge_positive(result)
    idx = find_max_sequence(result)
    # fix: id="24-2"
    delete_zero_at_last(result[idx])
    return f"{sum(result[idx])} {result[idx][0]} {result[idx][-1]}"


def summit():
    input()
    print(solution(list(map(int, input().split()))))


if __name__ == '__main__':
    summit()

def summit():
    string = input()
    result = 0
    q = list(map(int, string.split()))[1:]
    for now, destination in zip(([0]+q)[:-1], q):
        if now > destination:
            result += (now - destination) * 4
        else:
            result += (destination - now) * 6
        result += 5
    print(f"{result}", end="")


if __name__ == '__main__':
    summit()

from typing import Tuple


def num_to_decimal(num: str, radix: int) -> int:
    """
    将任意进制数转为10进制
    :param num:
    :param radix: 底
    """
    symbol_to_decimal = "0123456789abcdefghijklmnopqrstuvwxyz"
    result = 0
    for idx, i in enumerate(reversed(num)):
        # 测试点0：symbol不应该大于radix
        if symbol_to_decimal.index(i) >= radix:
            return -1
        result += symbol_to_decimal.index(i) * radix ** idx
    return result


def is_num_equal(num_radix_known: str, num_radix_unknown: str, radix: int) -> Tuple[bool, int]:
    """

    :param num_radix_known:
    :param num_radix_unknown:
    :param radix: num_radix_known的进制
    :return:
    """
    symbol_to_decimal = "0123456789abcdefghijklmnopqrstuvwxyz"
    is_equal = False
    num = num_to_decimal(num_radix_known, radix)

    min_radix = 0
    max_radix = num+1  # 记得+1测试点0
    while min_radix <= max_radix:
        mid_radix = int((min_radix + max_radix)/2)
        mid_num = num_to_decimal(num_radix_unknown, mid_radix)
        if mid_num == num:
            is_equal = True
            radix = mid_radix
            break

        if mid_num > num:
            max_radix = mid_radix - 1

        if mid_num < num:
            min_radix = mid_radix + 1

    # 测试点19
    if max(symbol_to_decimal.index(i)+1 for i in num_radix_unknown) > radix:
        is_equal = False
    return is_equal, radix


def summit():
    num1, num2, tag, radix = input().split()
    if int(tag) == 1:
        is_equal, radix = is_num_equal(num1, num2, int(radix))
    else:
        is_equal, radix = is_num_equal(num2, num1, int(radix))

    if is_equal:
        print(radix, end="")
    else:
        print("Impossible", end="")


if __name__ == '__main__':
    summit()

from functools import reduce


def summit():
    mapper = {
        0: "W",
        1: "T",
        2: "L"
    }
    maxOdds = []
    for _ in range(3):
        maxOdds.append(
            max(
                [(idx, float(i)) for idx, i in enumerate(input().split())],
                key=lambda x: x[1]
            )
        )
    print(f"{' '.join(mapper[x[0]] for x in maxOdds)} {(reduce(lambda a,b:a * b[1], maxOdds, 1)*0.65 - 1)*2:.2f}", end="")


if __name__ == '__main__':
    summit()

from typing import Dict, List


def summit():
    studentsNum, checkNum = map(int, input().split())
    students: Dict[str, List[int]] = {}
    result = ""

    # 读入
    for _ in range(studentsNum):
        infos = input().split()
        students[infos[0]] = list(map(int, infos[1:]))
        students[infos[0]].insert(0, int(sum(students[infos[0]])/3))

    studentsItem = students.items()

    # 对每门学科各自排序
    rankA = list(dict(sorted(studentsItem, key=lambda x: x[1][0], reverse=True)).keys())
    rankC = list(dict(sorted(studentsItem, key=lambda x: x[1][1], reverse=True)).keys())
    rankM = list(dict(sorted(studentsItem, key=lambda x: x[1][2], reverse=True)).keys())
    rankE = list(dict(sorted(studentsItem, key=lambda x: x[1][3], reverse=True)).keys())

    # 对每一个请求输出最高排名, 排序优先级ACME
    ranks = [rankA, rankC, rankM, rankE]

    # 修正排名
    # _ranks = [{}] * 4:这样子每个的{}的索引都相同
    # rankId：第i类成绩，0：平均成绩，1：c语言，2：数学，3：英语
    _ranks = [{}, {}, {}, {}]
    for rankId, rank in enumerate(ranks):
        _ranks[rankId][rank[0]] = 1  # 让第一个排名第一
        compare = students[rank[0]][rankId]  # 获得第一个成绩
        rightRank = 1  # 真正的排名是1
        # idx：学生编号
        for num, idx in enumerate(rank[1:]):
            if compare == students[idx][rankId]:
                _ranks[rankId][idx] = rightRank  # 和上一个的排名相同
            else:
                compare = students[idx][rankId]
                rightRank = num + 2
                _ranks[rankId][idx] = rightRank

    ranks = _ranks

    mapper = {
        0: 'A',
        1: 'C',
        2: 'M',
        3: 'E'
    }
    for _ in range(checkNum):
        request = input()
        try:
            minIdx = min(enumerate(ranks), key=lambda x: x[1][request])[0]
            result += f"{ranks[minIdx][request]} {mapper[minIdx]}\n"
        except KeyError:  # 没有这号学生
            result += f"N/A\n"

    print(result, end='')


if __name__ == '__main__':
    summit()